package summary;


import java.util.TreeSet;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/13 15:13
 * https://leetcode-cn.com/problems/contains-duplicate-iii/
 */
public class Title220 {

    /**
     * 双指针暴力
     * @param nums
     * @param k
     * @param t
     * @return
     */
    public static boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        for (int left = 0; left < nums.length; left++) {
            for (int right = left + 1; right < nums.length && right <= k + left; right++) {
                long temp = (long)nums[right] - (long)nums[left];
                if (Math.abs(temp) <= t) {
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean containsNearbyAlmostDuplicate1(int[] nums, int k, int t) {
        //自动从大到小进行排序
        TreeSet<Long> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            //abs(nums[i] - nums[j]) <= t      nums[j] - t <= nums[i] <= nums[j] + t
            Long ceiling = set.ceiling((long) nums[i] - (long) t);
            if (ceiling != null && ceiling <= (long) nums[i] + t) {
                return true;
            }
            set.add((long) nums[i]);
            //[i-k, i] abs(i - j) <= k
            if (i >= k) {
                set.remove((long) nums[i - k]);
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums = {1,5,9,1,5,9};
        int k = 2;
        containsNearbyAlmostDuplicate1(nums, k, 3);
    }
}
